package com.example.hot100;

import com.example.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Leetcode213_Rob2_Leetcode337_Rob3 {
    public static void main(String[] args) {
//        int[] nums = {1, 2, 3, 1};
//        System.out.println(new Solution2().rob(nums));

        //   3
        //  / \
        // 2   3
        //  \   \
        //   3   1
//        TreeNode root = new TreeNode(3);
//        root.left = new TreeNode(2);
//        root.left.right = new TreeNode(3);
//        root.right = new TreeNode(3);
//        root.right.right = new TreeNode(1);
//        System.out.println(new Solution3().rob(root));

        //     3
        //    / \
        //   4   5
        //  / \   \
        // 1   7   1

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(7);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(1);
        System.out.println(new Solution3().rob(root));
    }

    /**
     *  同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
     *  给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
     *
     *  示例 1：
     * 输入：nums = [2,3,2]
     * 输出：3
     * 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
     *
     *  示例 2：
     * 输入：nums = [1,2,3,1]
     * 输出：4
     * 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     *      偷窃到的最高金额 = 1 + 3 = 4 。
     *
     *  示例 3：
     * 输入：nums = [0]
     * 输出：0
     */
    static class Solution2 {
        /**
         * 动态规划
         * 偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；
         * 偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋
         * 两种区间的较大值即为结果
         * 这就转化成了leetcode198 的问题(动态规划)
         *
         * @param nums
         * @return
         */
        public int rob1(int[] nums) {
            if (nums.length == 1) return nums[0];
            else if (nums.length == 2) return Math.max(nums[0], nums[1]);
            return Math.max(robRange(nums, 0, nums.length - 2), // 偷第一间就不能偷最后一间
                    robRange(nums, 1, nums.length - 1)); // 不偷第一间就能偷最后一间
        }

        private int robRange(int[] nums, int start, int end) {
            int dp1 = nums[start], dp2 = Math.max(nums[start], nums[start + 1]);
            for (int i = start + 2; i <= end; i++) {
                int tmp = dp2;
                dp2 = Math.max(dp2, dp1 + nums[i]);
                dp1 = tmp;
            }
            return dp2;
        }

        public int rob(int[] nums) {
            return rob1(nums);
        }
    }

    /**
     * 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。
     *  这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。
     *  一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
     *  如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
     *  计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
     *
     *  示例 1:
     *  输入: [3,2,3,null,3,null,1]
     *      3
     *     / \
     *    2   3
     *     \   \
     *      3   1
     * 输出: 7
     * 解释:小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
     *
     *  示例 2:
     *  输入: [3,4,5,1,3,null,1]
     *      3
     *     / \
     *    4   5
     *   / \   \
     *  1   3   1
     * 输出: 9
     * 解释:小偷一晚能够盗取的最高金额= 4 + 5 = 9.
     */
    static class Solution3 {
        /**
         * 每个节点可选择偷或者不偷两种状态
         *   当前节点选择偷时，那么两个孩子节点就不能选择偷了
         *   当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)
         *
         *   当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
         *   当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
         *
         * @param root
         * @return
         */
        public int rob3(TreeNode root) {
            int[] res = robWithArr(root); //res[0]代表不偷当前节点的最大获益; res[1]代表偷当前节点的最大获益
            return Math.max(res[0], res[1]);
        }

        private int[] robWithArr(TreeNode root) {
            if (root == null) return new int[2];
            int[] result = new int[2];

            int[] leftRes = robWithArr(root.left);
            int[] rightRes = robWithArr(root.right);

            result[0] = Math.max(leftRes[0], leftRes[1]) + Math.max(rightRes[0], rightRes[1]);
            result[1] = root.val + leftRes[0] + rightRes[0];

            return result;
        }

        /**
         * 优化：使用HashMap记录已经计算过的节点的值
         * HashMap key 节点; value 节点对应的最大获益结果
         * @param root
         * @return
         */
        public int rob2(TreeNode root) {
            return robWithMap(root, new HashMap<>());
        }

        private int robWithMap(TreeNode root, Map<TreeNode, Integer> dpMap) {
            if (root == null) return 0;
            if (dpMap.containsKey(root)) return dpMap.get(root); // map中已经存在了某个节点的值，则直接获取
            int res1 = root.val;
            if (root.left != null)
                res1 += robWithMap(root.left.left, dpMap) + robWithMap(root.left.right, dpMap);
            if (root.right != null)
                res1 += robWithMap(root.right.left, dpMap) + robWithMap(root.right.right, dpMap);

            int res2 = robWithMap(root.left, dpMap) + robWithMap(root.right, dpMap);
            int result = Math.max(res1, res2);
            dpMap.put(root, result);
            return result;
        }

        /**
         * dp暴力法：
         * 在于是否选择根节点
         * 选择了根节点就不能再选择左右子节点，可以选择孙子节点(如果有)
         * 不选择根就选择左右子节点
         * 两者取较大值即可
         * @param root
         * @return
         */
        public int rob1(TreeNode root) {
            if (root == null) return 0;
            // 情况一:选择根节点 + 四个孙子节点
            int res1 = root.val;
            if (root.left != null) res1 += rob1(root.left.left) + rob1(root.left.right);
            if (root.right != null) res1 += rob1(root.right.left) + rob1(root.right.right);

            // 情况二:不选择根节点，就可以选择左右两个子节点
            int res2= rob1(root.left) + rob1(root.right);

            return Math.max(res1, res2);
        }

        public int rob(TreeNode root) {
            return rob3(root);
        }
    }
}
